871. Minimum Number of Refueling Stops

Posted on | In

871. Minimum Number of Refueling Stops

description:

TA car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

解答

这道题可以用最大堆的思维去理解

假设车一开始有n升油，一升油可以跑1公里，那么我们可以先让车跑n公里，看看在这n公里内有几个加油站，然后选择油最多的加油站进行加油（假设这个加油站的油量为t），然后再看（n + t）升油可以跑几公里，然后再次挑选油最多的加油站进行加油。在这个过程中统计加油次数。

在这个过程中用优先队列，里面按照油量的多少，从大到小存放可以加的油。

该题的结束条件是，当车可以跑的公里数大于终点的公里数，那么就返回加油次数。或者当没油可加，即优先队列为空时，返回 -1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    priority_queue <int> pq;
    int count = 0;
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        ///stations为空，判断startFuel和target的关系
        if(stations.empty()) {

            return startFuel >= target ? 0 : -1;
        }
        int i = 0;
        while(1) {
            if (startFuel >= target)
                return count;
            while(i < stations.size() && stations[i][0] <= startFuel) {
                pq.push(stations[i][1]);
                i ++;
            }
            if (pq.empty()) return -1;
            startFuel += pq.top();
            pq.pop();
            count++;
        }
        return count;
    }
};